Міністерство освіти і науки України
Національний університет «Львівська політехніка»
Кафедра ЕОМ
Звіт
з лабораторної роботи № 1
з курсу "Дискретна математика"
Мета: засвоїти на практиці знання з теорії множин, підготувавши відповідну програму. Короткі теоретичні відомості:
Множини є основними об’єктами вивчення у дискретній математиці. Множина це невпорядкована сукупність об’єктів, які називають елементами множини.
Елементами можна вважати довільні об’єкти, які можуть бути названі або означені за допомогою правила, що задає належність до множини.
Для будьякого елемента можна встановити, чи належить він множині X. Запис x ∈X означає приналежність елемента x до множини X, а символ «∈» це знак приналежності деякого елемента до множини X.
Відношення R ≤ A×A називається антисиметричним, якщо з x R y і
y R x випливає, що x = y для всіх x,y ∈ X.
Відношення R, визначене на множині A можна задавати квадратною матрицею M, кожний рядок і стовпчик якої відповідають одному елементу множини A.
Якщо елемент a i ∈ A знаходиться у відношенні R до елемента a j , то елемент m ij матриці M буде приймати значення true , у протилежному випадку false.
В ряді реалізацій приймають замість значення true 1, a false 0
З допомогою квадратної матриці розмірності n×n , котра задає деяке бінарне відношення на множині потужності n , легко перевірити основні властивості цього відношення. Відповідну процедуру можна побудувати на будь-якій алгоритмічній мові.
Завдання лабораторної роботи:
Варіант 13
Розробити програмне забезпечення яке перевіряє антисиметричність.
Множина X={всі студенти НУ «ЛП»} x,y ∈ R якщо різниця номерів місяців народження студентів x і y невідємна
Алгоритм програми:.
Побудова квадратної матриці
Перевірка симетричності відношення шляхом підстановки в відношення кожної пари елементів множини X.
Вивід на екран результату перевірки у вигляді матриці значень “1” та ”0” і текстового рядка
Реалізація програми на мові програмування C++:
#include <iostream>
#include <stdio.h>
#include <iomanip>
#include <time.h>
#include <locale.h>
#include <math.h>
using namespace std;
//Задано відношення x-y <= 0; x,y є X
// X = {місяці народження всіх студентів НУ "ЛП" }
int main()
{
setlocale(LC_ALL, ".1251");
int arr[13] = {0,1,2,3,4,5,6,7,8,9,10,11,12};
int i, j;
int n = 13;
cout << endl;
cout << "-----------------------------------" << endl;
for (i = 1; i < n; i++)
{
cout << arr[i] << " ";
}
cout << endl;
cout << "-----------------------------------" << endl;
int **result;
result = new int*[n];
for (i = 0; i < n; i++)
{
result[i] = new int[n];
}
for (i = 0; i < n; i++)
{
result[i][0] = arr[i];
}
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
result[i][j] = result[j][i];
}
}
for (i = 1; i < n; i++)
{
for (j = 1; j < n; j++)
{
int x = result[i][0];
int y = result[0][j];
int rizn1 = (x - y);
int rizn2 = (y - x);
if (rizn1 >= 0 & rizn2>= 0)
result[i][j] = 1;
else
result[j][i] = 0;
}
}
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
cout << setw(3) << result[i][j];
cout << endl;
}
int p=0;
for (i = 1; i < n; i++)
{
for (j = 1; j < n; j++)
{
if (result[i][j] == 1)
{
p++;
if (i!=j)
{
p=0;
continue;
}
}
}
}
if (p == n-1)
{
cout << endl;
cout << "Вiдношення антисиметричне" << endl;
}
else
{
cout << endl;
cout << "Вiдношення не антисиметричне" << endl;
}
for (i = 0; i < n; i++)
{
delete[] result[i];
}
delete[] result;
system("pause");
return 0;
}
Результат роботи програми:
/
Висновок: я засвоїв і використав на практиці знання теорії множин, склавши відповідну програму.
